#ifndef SUFFIX_TREE_HPP
#define SUFFIX_TREE_HPP

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <map>

class sNode;
class sEdge;
typedef std::map<int, sEdge*> _transMap;
typedef std::map<int, sEdge*>::iterator mapItr;

class sNode {
    private:
	bool _leaf;
	bool _root;
	bool _explicit;
	sEdge *_parEdge;
	sNode *_sLink;
	int _id;
	static int _count;
	sNode (const sNode&);
	const sNode& operator=(const sNode&);
    public:
	sNode(bool root) {
	    _id = ++_count;
	    _root = root;
	}
	sNode(sEdge *e) {
	    _id = ++_count;
	    _parEdge = e;
	    _leaf = true;
	    _root = false;
	}
	sNode(bool r, bool e, bool l) {
	    _id = ++_count;
	    _root = r;
	    _explicit = e;
	    _leaf = l;
	}
	~sNode() {}/*everything will be deleted through destructor of edge*/
	bool isLeaf() const { return _leaf; }
	void sLink(sNode *link) { _sLink = link; }
	sNode* sLink() { return _sLink; }
	void leaf(bool flag) { _leaf = flag; }
	int id() { return _id; }
	std::pair<sNode*, int> walkTree(std::string&, int, _transMap&,
		std::vector<std::string*>&);
	void serialize (std::ofstream &out, _transMap* map, std::vector<std::string*>&);
};

class sEdge {
    private:
	sNode *_from;
	sNode *_to;
	int _firstCharIndex;
	int _lastCharIndex;
	int _wordIndex;/*for generalized suffix tree*/
	sEdge (const sEdge&);
	const sEdge& operator=(const sEdge&);
    public:
	sEdge(sNode *frm, int start, int end, int wIndex) {
	    _from = frm;
	    _from->leaf(false);
	    _firstCharIndex = start;
	    _lastCharIndex = end;
	    _wordIndex = wIndex;
	}
	sEdge(sNode *frm, sNode *to, int start, int end) {
	    _from = frm;
	    _from->leaf(false);
	    _to = to;
	    _firstCharIndex = start;
	    _lastCharIndex = end;
	    _wordIndex = -1;
	}
	~sEdge() {
	    if (_from) {
		delete _from;
		_from = NULL;
	    }
	    if (_to) {
		delete _to;
		_to = NULL;
	    }
	}
	void to(sNode *to) { _to = to; }
	sNode* from() { return _from; }
	sNode* to() { return _to; }
	int wordIndex() { return _wordIndex; }
	int startIndex() { return _firstCharIndex; }
	int endIndex() { return _lastCharIndex; }
};

class suffixTree {
    private:
	sNode *_root;
	sNode *_exp;
	_transMap *transMap;
	std::vector<std::string*> *words;
	suffixTree (const suffixTree&);
	const suffixTree& operator=(const suffixTree&);
    public:
	suffixTree() {
	    _root = new sNode(true, false, false);
	    _exp = new sNode(false, true, false);
	    _root->sLink(_exp);
	    transMap = new _transMap();
	    words = new std::vector<std::string*>();
	};
	~suffixTree() {
	    sNode *f = NULL, *t = NULL;
	    sEdge *e = NULL;
	    for (mapItr itr = transMap->begin(); itr != transMap->end(); itr++) {
		e = itr->second;
		delete e;
		e = NULL;
	    }
	    delete transMap;
	    transMap = NULL;
	    delete words;
	    words = NULL;
	}
	void insert(std::string&);
	std::pair<sNode*, int>* update(sNode*, int, int, int);
	std::pair<sNode*, int>* canonize(sNode*, int, int, int);
	std::pair<bool, sNode*>* testAndSplit(sNode*, int, int, char, int);
	void serialize(std::ofstream &out);
};

#endif
